Negative (and Positive) Circles in Signed Graphs: A Problem Collection

摘要

A signed graph is a graph whose edges are labelled positive or negative. Thesign of a circle (cycle, circuit) is the product of the signs of its edges.Most of the essential properties of a signed graph depend on the signs of itscircles. Here I describe several questions regarding negative circles and theircousins the positive circles. Topics include incidence between signed circlesand edges or vertices, characterizing signed graphs with special circleproperties, counting negative circles, signed-circle packing and covering,signed circles and eigenvalues, and directed cycles in signed digraphs. A fewof the questions come with answers.